#include <stdio.h>
#define  N  16

/* https://c.biancheng.net/view/3448.html */

void HeapAdjust(int data[], int s, int m)
/* 在data[s..m]所构成的一个元素序列中，除了data[s]外，其余元素均满足大顶堆的定义 */
/* 调整元素data[s]的位置，使data[s..m]成为一个大顶堆 */
{
    int tmp, j;
    tmp = data[s];  /*备份元素data[s]，为其找到适当位置后再插入*/
    for(j = 2*s+1; j <= m; j = j*2+1) {     /*沿值较大的孩子节点向下筛选*/
        if(j < m && data[j] < data[j+1]) ++j;   /* j是值较大元素的下标 */
        if(tmp >= data[j]) break;   /* 如果当前结点比最大的孩子结点的值还大，则不需要对此结点进行筛选，直接略过 */
        data[s] = data[j]; s = j;   /* 用s记录待插入元素的位置下标 */
    }/*for*/
    data[s] = tmp;      /*将备份元素插入由s所指出的插入位置*/
}/*HeapAdjust*/

void HeapSort(int data[], int n)    /*数组data[0..n-1]中的n个元素进行堆排序*/
{
    int i, tmp;
    for(i = n/2-1; i >= 0; --i)     /*将data[0..n-1]调整为大根堆*/
        HeapAdjust(data, i, n-1);
    for(i = n-1; i > 0; --i)
    {
        tmp = data[0];
        data[0] = data[i];
        data[i] = tmp;  /*堆顶元素data[0]与序列末的元素data[i]交换*/
        HeapAdjust(data, 0, i-1);   /*待排序元素的个数减1，将data[0..i-1]重新调整为大根堆*/
    }/*for*/
}/*HeapSort*/

int main(int argc, char * argv[]) {
    int arr[N] = {49, 38, 65, 97, 76, 13, 27, 49};
    //int arr[N] = {55, 60, 40, 80, 65, 15, 5, 75, 49, 38, 65, 97, 76, 13, 27, 49};
    HeapSort(arr, N);
    for(int i = 0; i < N; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}